     \noindent
     The classical GP specification (\cite{koza92genetic}) requires the definitions of the terminals
     and functions of a GP system to satisfy the {\em closure} requirement.
     %Closure is the constraint that
%     all the elements in the program's parse tree must be of the same type and that no evaluation
%     step will produce a run-time error (so that for example, division by 0 is artificially made safe).
%      Koza declares that c
      Closure is  satisfied  when ``any possible composition of functions and terminals
      produces a valid executable computer program" (\cite{koza98}). In Koza's systems,
      closure usually implies using a monomorphic programming language
      to code the genotypes. This in terms implies carefully defining the terminals and
      functions so as to not introduce multiple data types.
    % Typical programming syntax usually includes ``administration structures" such
%     as decisions and loops. These act on some boolean type argument.
%     In GP, these structures are not directly related to the problem
%     that is being solved, but are still included because they are
%     needed for the construction of the program logic. The choices and definitions of functions in
%     typical GP systems
%     are necessarily influenced by the closure constraint. .
     In Koza's systems, general definitions for decision functions or
     predicates are typically avoided to remove the need for a Boolean type.
     Instead, combined constructs such as (\ref{DEFEX2}) are used.
    \begin{equation}\label{DEFEX2}
    (if\_smaller\_than\_else\mbox{ }x\mbox{ }y\mbox{ }u\mbox{ }v)
     \end{equation}

    \noindent
    Where $x,y,u,v$ are of the same type.
%    This is because a structure such as expression (\ref{DEFEX1})
%    requires a type system with the first argument
%    of the $IF$ function evaluating to a boolean.
%    \begin{equation}\label{DEFEX1}
%    (IF(SMALLER\_THAN\mbox{ }x\mbox{ }y)\mbox{ }u\mbox{ }v)
%    \end{equation}
%    \noindent
%    S-expression \ref{DEFEX2} on the other hand eliminates the need to
%    introduce a type system.
%    %Closure limits the applicability of GP.
    This style of function definition introduces two issues:
    \begin{enumerate}
    \item In order to increase the expressive power of the language, the system's designer is
    forced to define several functions specialized
    in the same way ($IF\_EQ\_ELSE$, $IF\_LESS\_THAN\_0\_ELSE$,...),
    making the syntax pre-defined for the GP heavier than needed.
    \item It lacks flexibility. Functions defined in this way prevent the evolution of specialized problem
    specific programming constructs. For example, it would be impossible for a GP system that
    respects the closure constraint to evolve an expression such as:
    \begin{equation}
    IF\_ELSE((SMALLER\_THAN\mbox{ }x\mbox{ }y)\mbox{ }OR\mbox{ }(EQ\mbox{ }0\mbox{ }x)),\ldots
    \end{equation}
    \end{enumerate}
    %only becomes possible on specific user-defined
%    operations ($SMALLER\_THAN$, $EQUAL$), so that more complicated branching conditions can not be formed
%    (for example).
    \noindent
    Koza has realized this shortcoming and added a mechanism called
    {\em constrained syntactic structures} \cite{koza92genetic}  to relax the closure property.
    \subsection{Constrained syntactic structures}\label{ConstrainedPreviousWork}
    \noindent
    Constrained syntactic structures define a set of problem-specific syntactic rules specifying
    which terminals and functions are allowed to be the child nodes of every function in the program trees.
    They are a way to enforce data type constraints to only generate parse trees satisfying these constraints (``legal'' parse trees). Constrained syntactic structures are used for problems requiring data typing. They define problem-specific syntactic rules that specify which terminals and functions are allowed to be the child nodes of functions in GP program trees.

     \subsection{Context-free grammar approach}
     \noindent
     Also noting that the requirement of closure makes many program structures difficult to express, \cite{whigham95grammaticallybased} proposed the use of {\em context free grammars} (CFGs) to specify the structure  of the system's programs. A context free grammar describes the admissible constructs of a language. Note in the following definition that {\em non-terminals} and {\em terminals} have different meanings in GP and in CFG.
    \begin{definition}
    A CFG is a 4-tuple, $\{S,N,T,P\}$ where $S$ is the start symbol, $N$ is a set of non-terminal symbols, $T$ is the set of terminal symbols and $P$ are the production rules.
    \end{definition}
    \noindent
    In \CFGBGP{}, program trees are derivation trees and they are generated from the grammar. At the root of each derivation tree is the start symbol $S$. The trees are iteratively built up from the start symbol by re-writing each non-terminal symbol into one of its derivations. Crossover  is restricted to swapping subtrees built on the same non-terminal (in the CFG sense) symbol.
%   This is done by rewriting the axioms of the grammar, using its rewrite rules. A specialized algorithm is used to generate legal program trees. the grammar allows the user to bias the initial GP structures, and automatically ensure typing and syntax are maintained by manipulating the explicit derivation tree from the grammar
     \newline
     \newline
     \noindent
     For rules whose non-terminal can be rewritten recursively, an upper bound of the number of recursive rewritings of this rule is specified and used to limit the size of the program tree.

     \subsection{Typed GP systems}\label{TypedPreviousWork}
     \noindent
      As every \pl{} can be formulated using a grammar, typed GP system
      are a subset of grammar-based GP. There are two reasons to consider
      using a type system as a GP representation scheme:
      eliminating the closure constraint and narrowing the system's
      search space. In this section other GP systems based on a
      typed representation and their relationship to the system proposed in this thesis are discussed.
     \subsection{Strongly Typed Genetic Programming}
         \noindent
    In \cite{montana93strongly}, Montana shows how types can be
    used to eliminate the closure
    constraint of un-typed genetic programs and
    to restrict the search space of genetic programs. Montana named the method
    {\em Strongly Typed Genetic Programming} (STGP). In STGP,
    each function has a specified type for each argument and for the value
    it returns. For example, (\ref{eq89}) defines a function that
    takes 2 arguments of type $TYPE_1$ and returns an object of type $TYPE_2$:
    \begin{equation}\label{eq89}
    func:TYPE_1\rightarrow TYPE_1\rightarrow TYPE_2
    \end{equation}
    Terminals are also typed, as in $true:Boolean$

    \subsubsection{STGP and polymorphism}
    \noindent
    {\bf Generic functions:} The basic STGP formulation is equivalent to Koza's approach
    to constrained syntactic structures
    (section \ref{ConstrainedPreviousWork}) and has the same limitation:
     The need to specify multiple functions which perform the same operation.
%    For example, consider the classic example: a typed branching function IFTE:
%    \begin{equation}\label{TypedIfEx1}
%    IFTE:Boolean\rightarrow TYPE_1\rightarrow TYPE_1\rightarrow TYPE_1
%    \end{equation}
%    \noindent
%    The IFTE function of (\ref{TypedIfEx1}) is usable
%    as a decision function between two objects of type $TYPE\_1$,
%    but not in any other context. This implies that different versions
%    of the same function need  to be defined to handle other data types.
%    \newline
%    \newline
%    \noindent
    Montana resolves the issue by using {\em generic functions}. These are functions that
    are defined on named lists of argument types and have their return types infered when
    they are embedded in a new tree not built from a crossover operation.
  %  For example, the branching function would be typed:
%    \begin{equation}\label{TypedIfEx2}
%    IFTE:BOOL\rightarrow X\rightarrow X\rightarrow X
%    \end{equation}
%    $X$ is a type variable that gets replaced by a type when a program is  constructed
%    at the beginning of the GP's run.
     After a generic function has been instantiated (by being embedded in a new tree) it
     is and behaves as a standard typed function. This is also how it is passed on to the program's
     descendants.
%    \paragraph{Table possibility table}
        Montana uses a table-lookup mechanism to produce legal
        parse trees.A type possibilities table is computed beforehand to
        specify all the types that are possible to be generated at each tree
        depth level. This table provides type constraints to
        the function selection procedure used to generate type-correct programs.
        During the creation of the initial population, each parse tree is grown top-down by
        randomly choosing functions and terminals and verifying their validity
        as possible tree nodes against the type possibility table.
    \newline
    \newline
    \noindent
    \textbf{Generic types:} Generic functions eliminate the need to specify multiple functions
    which perform the same operation on different types.
    To produce generic programs in STGP, Montana
    also implemented a {\em generic type} system. {\em Generic programs}
    are programs that have generic data types as input
    or output types. The
    generic data types are instantiated when the generic program
    is executed. Since generic data types can be instantiated with
    many different type values, the generated programs are
    generic programs.
    \newline
    \newline
    \noindent
    \cite{haynes95strongly}
    applied STGP to the problem of evolving cooperation strategies in a predator prey environment.
    They reported that the solutions produced by a STGP system consistently
    outperformed the solutions produced by a standard GP system. They suggest
    that the reduced search space is the
    cause of the performance improvements. They also showed that the programs generated by STGP
    tend to be easier to understand. Following these encouraging results, \cite{haynes96type} proposes the extension of STGP with a type hierarchy mechanism and describes an application to the problem of finding all the cliques in an indirected or directed graph.
    \newline
    \newline
    \noindent
    There are three basic limitations with STGP's method:
    \begin{enumerate}
    \item {\bf Type possibilities table and table-lookup mechanism to instantiate type variables:}
    \noindent
    With STGP, when a parse tree is generated and a generic
function is considered for inclusion, the underlying GP system must
insure that the new element will make it possible to select legal
subtrees. For generic functions, the GP has to loop over all ways to
combine types from a type possibility table that is maintained
centrally by the system. Here, I propose \SF{} because it
decentralizes the process of type checking during tree generation.
When inserting any function node (even for polymorphic function)
into a parse tree that is syntactically equivalent to a \SF{ } term,
it is always possible to infer the legality of the resulting tree by
looking {\em at nothing else but the parse tree and the function}.
This eliminates the need for type possibility tables.
    \item {\bf Evolving polymorphic functions and structures: } Polymorphic functions are instantiated with solid
    types when included in a newly spawned tree. Crossover acts on functions and terminals that
    are not polymorphic anymore. There is no possibility of evolving
    functions defined for all types. There is no possibility of
    evolving structures such as trees or lists.
    \item {\bf Lack of support for higher-order functions: } SGTP has no
    general support for growing functions which take functions as arguments
    and/or return functions as results.
    \end{enumerate}

     \subsection{The PolyGP system}\label{PolyGP}\input{PolyGP}
